package 竞赛.周赛214;

import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 第二题.java
 * @Description TODO
 * @createTime 2020年11月08日 10:48:00
 * 如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
 *
 * 给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
 *
 * 字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。
 * 思路：用哈希表存储 每个字符的个数 找出重复
 */
public class 第二题 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int aaabbbcc = solution.minDeletions("bbcebab");
        System.out.println(aaabbbcc);
    }
    static class Solution {
        public int minDeletions(String s) {
            int res=0;
            HashMap<Character,Integer> map=new HashMap<>();
            for(int i=0;i<s.length();i++){
                map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
            }

            ArrayList<Integer> list=new ArrayList<>();
            for(int a:map.values()){
                list.add(a);
            }


            list.sort(Comparator.naturalOrder());

            for(int i=0;i<list.size()-1;i++){
                if(list.get(i).equals(list.get(i+1))){
                    int temp=list.get(i);
                    while(list.contains(temp)){
                        temp--;
                        res++;
                    }
                    if(temp==0){
                        continue;
                    }
                    list.set(i,temp);
                }
            }
        return  res;
        }
    }


}
